<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.1">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/32x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/16x16.png">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic|Lato', 'Microsoft Yahei Light:300,300italic,400,400italic,700,700italic|Cambria', 'Microsoft Yahei Light:300,300italic,400,400italic,700,700italic|Verdana', Lato, 'Microsoft Yahei Light:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"yoursite.com","root":"/","scheme":"Mist","version":"7.8.0","exturl":false,"sidebar":{"position":"right","display":"hide","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="Problem 497 Drunken Tower of Hanoi Bob is very familiar with the famous mathematical puzzle&#x2F;game, “Tower of Hanoi,” which consists of three upright rods and disks of different sizes that can slide on">
<meta property="og:type" content="article">
<meta property="og:title" content="Problem 497">
<meta property="og:url" content="http://yoursite.com/497/index.html">
<meta property="og:site_name" content="Project Euler | 欧拉计划">
<meta property="og:description" content="Problem 497 Drunken Tower of Hanoi Bob is very familiar with the famous mathematical puzzle&#x2F;game, “Tower of Hanoi,” which consists of three upright rods and disks of different sizes that can slide on">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://projecteuler.net/project/images/p497_hanoi.gif">
<meta property="og:image" content="https://projecteuler.net/project/images/p497_hanoi.gif">
<meta property="article:published_time" content="2015-01-11T12:00:00.000Z">
<meta property="article:modified_time" content="2015-10-28T02:56:44.000Z">
<meta property="article:author" content="sx349">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://projecteuler.net/project/images/p497_hanoi.gif">

<link rel="canonical" href="http://yoursite.com/497/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>Problem 497 | Project Euler | 欧拉计划</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">Project Euler | 欧拉计划</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-problem">

    <a href="/problems" rel="section"><i class="fa fa-tags fa-fw"></i>题目</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/497/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.png">
      <meta itemprop="name" content="sx349">
      <meta itemprop="description" content="Project Euler | 欧拉计划 中文翻译站">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Project Euler | 欧拉计划">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          Problem 497
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">题目发布于</span>

              <time title="发布时间：2015-01-11 04:00:00" itemprop="dateCreated datePublished" datetime="2015-01-11T04:00:00-08:00">2015-01-11</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">翻译更新于</span>
                <time title="更新时间：2015-10-27 19:56:44" itemprop="dateModified" datetime="2015-10-27T19:56:44-07:00">2015-10-27</time>
              </span>

          

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <hr>
<h1 id="Problem-497"><a href="#Problem-497" class="headerlink" title="Problem 497"></a><a href="https://projecteuler.net/problem=497" target="_blank" rel="noopener">Problem 497</a></h1><hr>
<p><strong>Drunken Tower of Hanoi</strong></p>
<p>Bob is very familiar with the famous mathematical puzzle/game, “Tower of Hanoi,” which consists of three upright rods and disks of different sizes that can slide onto any of the rods. The game begins with a stack of n disks placed on the leftmost rod in descending order by size. The objective of the game is to move all of the disks from the leftmost rod to the rightmost rod, given the following restrictions:</p>
<ol>
<li>Only one disk can be moved at a time.</li>
<li>A valid move consists of taking the top disk from one stack and placing it onto another stack (or an empty rod).</li>
<li>No disk can be placed on top of a smaller disk.</li>
</ol>
<p>Moving on to a variant of this game, consider a long room k units (square tiles) wide, labeled from 1 to k in ascending order. Three rods are placed at squares a, b, and c, and a stack of n disks is placed on the rod at square a.</p>
<p>Bob begins the game standing at square b. His objective is to play the Tower of Hanoi game by moving all of the disks to the rod at square c. However, Bob can only pick up or set down a disk if he is on the same square as the rod / stack in question.</p>
<p>Unfortunately, Bob is also drunk. On a given move, Bob will either stumble one square to the left or one square to the right with equal probability, unless Bob is at either end of the room, in which case he can only move in one direction. Despite Bob’s inebriated state, he is still capable of following the rules of the game itself, as well as choosing when to pick up or put down a disk.</p>
<p>The following animation depicts a side-view of a sample game for n = 3, k = 7, a = 2, b = 4, and c = 6:</p>
<center><img src="https://projecteuler.net/project/images/p497_hanoi.gif"></center>

<p>Let E(n,k,a,b,c) be the expected number of squares that Bob travels during a single optimally-played game. A game is played optimally if the number of disk-pickups is minimized.</p>
<p>Interestingly enough, the result is always an integer. For example, E(2,5,1,3,5) = 60 and E(3,20,4,9,17) = 2358.</p>
<p>Find the last nine digits of ∑<sub>1≤n≤10000</sub> E(n,10<sup>n</sup>,3<sup>n</sup>,6<sup>n</sup>,9<sup>n</sup>).</p>
<hr>
<p><strong>醉酒汉诺塔</strong></p>
<p>鲍勃非常熟悉著名的数学谜题汉诺塔：这个游戏包含了三根竖直的柱子和能够串在柱子上的不同大小的盘子。游戏的开始状态是n个盘子按从大到小的顺序依次串在最左边的柱子上；游戏的目标是在以下的限制条件下，把所有的盘子都串到最右边的柱子上：</p>
<ol>
<li>一次只能移动一个盘子。</li>
<li>一个有效的移动包括拿起一堆盘子最顶上的一个以及把它放在另一堆盘子的顶端（或者一个空的柱子上）。</li>
<li>每个盘子都不能放在比它小的盘子上。</li>
</ol>
<p>现在我们来玩这个游戏的一个变种，在一间k单位长并依次标上了1至k的房间里，三根柱子方别被摆在了标有a、b和c的位置，在a位置的柱子上有n个盘子。</p>
<p>鲍勃从位置b开始进行游戏，他的目标是像汉诺塔那样把所有盘子移动到位置c的柱子上，但是他只能在有柱子的地方捡起或放下盘子。</p>
<p>不幸的是，鲍勃喝醉了，每当他要移动的时候，他将以相同的概率向左或向右走一步，除非他是在房间的某个尽头，只能往另一个方向走。不过，Bob即使是在喝醉的状态下，依然能够按照游戏的规则来合理选择何时应该捡起或放下盘子。</p>
<p>下面的动画是一个简单游戏的侧面演示，这个游戏中n = 3，k = 7，a = 2，b = 4，c = 6：</p>
<center><img src="https://projecteuler.net/project/images/p497_hanoi.gif"></center>

<p>记E(n,k,a,b,c)是Bob按照最优的方式完成游戏所需要走过的路程的期望值，在这里“最优”的衡量标准是捡起盘子的次数最少。</p>
<p>非常有趣的是，计算结果总是一个整数，例如，E(2,5,1,3,5) = 60以及E(3,20,4,9,17) = 2358。</p>
<p>求∑<sub>1≤n≤10000</sub> E(n,10<sup>n</sup>,3<sup>n</sup>,6<sup>n</sup>,9<sup>n</sup>)的最后九位数字。</p>
<hr>

    </div>

    
    
    

      <footer class="post-footer">

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/496/" rel="prev" title="Problem 496">
      <i class="fa fa-chevron-left"></i> Problem 496
    </a></div>
      <div class="post-nav-item">
    <a href="/498/" rel="next" title="Problem 498">
      Problem 498 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          
    <div class="comments" id="gitalk-container"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#Problem-497"><span class="nav-text">Problem 497</span></a></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="sx349"
      src="/images/avatar.png">
  <p class="site-author-name" itemprop="name">Leonhard Euler(1707-1783)</p>
  <p class="site-description motion-element">Project Euler | 欧拉计划<br>中文翻译站</p>
</div>
  <div class="cc-license motion-element" itemprop="license">
    <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" class="cc-opacity" rel="noopener" target="_blank"><img src="/images/cc-by-nc-sa.svg" alt="Creative Commons"></a>
  </div>


  <div class="links-of-blogroll motion-element">
    <div class="links-of-blogroll-title"><i class="fa fa-link fa-fw"></i>
      友情链接
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-title">
          <a href="https://projecteuler.net/" title="https:&#x2F;&#x2F;projecteuler.net" rel="noopener" target="_blank">Project Euler</a>
        </li>
        <li class="links-of-blogroll-title">
          <a href="http://jakwings.is-programmer.com/Project_Euler" title="http:&#x2F;&#x2F;jakwings.is-programmer.com&#x2F;Project_Euler" rel="noopener" target="_blank">饮水思源汉化</a>
        </li>
        <li class="links-of-blogroll-title">
          <a href="http://sx349.github.io/" title="http:&#x2F;&#x2F;sx349.github.io" rel="noopener" target="_blank">译者博客</a>
        </li>
    </ul>
  </div>

      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 2001 – 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fas fa-calculator"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Project Euler | 欧拉计划</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://mist.theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Mist</a> 强力驱动
  </div>

        








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/muse.js"></script>


<script src="/js/next-boot.js"></script>




  




  
<script src="/js/local-search.js"></script>













  

  
      

<script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      loader: {
        source: {
          '[tex]/amsCd': '[tex]/amscd',
          '[tex]/AMScd': '[tex]/amscd'
        }
      },
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              let target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    (function () {
      var script = document.createElement('script');
      script.src = '//cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js';
      script.defer = true;
      document.head.appendChild(script);
    })();
  } else {
    MathJax.startup.document.state(0);
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  

<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.css">

<script>
NexT.utils.loadComments(document.querySelector('#gitalk-container'), () => {
  NexT.utils.getScript('//cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.js', () => {
    var gitalk = new Gitalk({
	  title       : document.title.substr(0,29),
      clientID    : '4ba99a8839c5e7dde683',
      clientSecret: '3984f7cad409553d6afde8dbc2c08fc425e7bbdc',
      repo        : 'pe-cn-comments',
      owner       : 'pe-cn',
      admin       : ['sx349'],
      id          : 'c356a374c88750c22ab73ec8a33d63de',
        language: '',
      distractionFreeMode: true
    });
    gitalk.render('gitalk-container');
  }, window.Gitalk);
});
</script>

</body>
</html>
